package concurrentsandbox;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

@SuppressWarnings("serial")
public class MergeSortWithFJ extends RecursiveAction {

	/**
	 * Merges two sorted lists into one
	 */
	private static int[] merge(int[] a, int[] b, int[] result) {
		int i = 0, j = 0, idx = 0;

		while ((i < a.length) && (j < b.length)) {
			if (a[i] <= b[j]) {
				result[idx] = a[i++];
			} else {
				result[idx] = b[j++];
			}
			idx++;
		}

		if (i < a.length) {
			for (; i < a.length; i++) {
				result[idx++] = a[i];
			}
		} else {
			for (; j < b.length; j++) {
				result[idx++] = b[j];
			}
		}
		return result;
	}

	private final int[] numbers;

	public MergeSortWithFJ(int[] numbers) {
		this.numbers = numbers;
	}

	@Override
	protected void compute() {
		switch (numbers.length) {
		case 1:
			// 1 is already sorted
			return;
		case 2:
			// list of two is easy to sort
			if (numbers[0] > numbers[1]) {
				int tmp = numbers[0];
				numbers[0] = numbers[1];
				numbers[1] = tmp;
			}
			return;
		default:
			// everything greater than 2 is split and then solved in parallel
			int listSize = numbers.length;
			int middleIndex = listSize / 2;
			int[] left = Arrays.copyOf(numbers, middleIndex);
			int[] right = Arrays.copyOfRange(numbers, middleIndex,
					numbers.length);
			invokeAll(new MergeSortWithFJ(left), new MergeSortWithFJ(right));
			merge(left, right, numbers);
		}
	}

	public static int[] solveUsingFj(int[] numbers, int nThreads) {
		ForkJoinPool fjPool = new ForkJoinPool(nThreads);
		fjPool.invoke(new MergeSortWithFJ(numbers));
		fjPool.shutdown();
		return numbers;
	}
}